package com.algorithm.liyc.practice;

/**
 * 替换空格
 * 请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
 *
 * @author Liyc
 * @date 2023/12/12 17:01
 **/

public class Solution25 {
    /**
     * 双指针法
     * ● 时间复杂度：O(n)
     * ● 空间复杂度：O(1)
     * @param s
     * @return
     */
    public String replaceSpace(String s) {
        if (s == null || s.length() == 0) {
            return s;
        }
        //扩充空间，空格数量2倍
        StringBuffer stringBuffer = new StringBuffer();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == ' ') {
                stringBuffer.append(" ");
            }
        }
        //若是没有空格直接返回
        if (stringBuffer.length() == 0) {
            return s;
        }
        //有空格情况 定义两个指针
        int left = s.length() - 1;//左指针：指向原始字符串最后一个位置
        s += stringBuffer;
        int right = s.length() - 1;//右指针：指向扩展字符串的最后一个位置
        char[] ches = s.toCharArray();
        while (left >= 0) {
            if (ches[left] == ' '){
                ches[right--] = '0';
                ches[right--] = '2';
                ches[right] = '%';
            } else {
                ches[right] = ches[left];
            }
            left--;
            right--;
        }
        return new String(ches);
    }
}
